/*
 * @lc app=leetcode.cn id=306 lang=typescript
 *
 * [306] 累加数
 */

// @lc code=start
function isAdditiveNumber(num: string): boolean {
  const n = num.length;

  // 验证区间是否合法
  const isValid = (secondStart: number, secondEnd: number, num: string): boolean => {
    const n = num.length;
    let firstStart = 0;
    let firstEnd = secondStart - 1;
    while (secondEnd <= n - 1) {
      const third = buildString(firstStart, firstEnd, secondStart, secondEnd, num);
      const thirdStart = secondEnd + 1;
      const thirdEnd = secondEnd + third.length;
      if (thirdEnd >= n) break;

      if (num.slice(thirdStart, thirdEnd + 1) !== third) break;
      // 遍历到最后一个数字，是合法序列
      if (thirdEnd === n - 1) return true;
      firstStart = secondStart;
      firstEnd = secondEnd;
      secondStart = thirdStart;
      secondEnd = thirdEnd;
    }
    return false;
  };

  // 根据前2个数的范围，构建第3个数
  // 为了避免大数溢出，将数字按位放入数组，最后合并成字符串
  const buildString = (
    firstStart: number,
    firstEnd: number,
    secondStart: number,
    secondEnd: number,
    num: string
  ): string => {
    const third = [];
    let carry = 0;
    let current = 0;
    while (firstStart <= firstEnd || secondStart <= secondEnd || carry !== 0) {
      current = carry;
      if (firstStart <= firstEnd) {
        current += Number(num[firstEnd]);
        firstEnd--;
      }
      if (secondStart <= secondEnd) {
        current += Number(num[secondEnd]);
        secondEnd--;
      }
      carry = (current / 10) >> 0;
      current %= 10;
      third.push(String(current));
    }

    return third.reverse().join('');
  };

  // 枚举第二个数的范围[secondStart, secondEnd]
  for (let secondStart = 1; secondStart < n - 1; secondStart++) {
    if (num[0] === '0' && secondStart !== 1) break;
    for (let secondEnd = secondStart; secondEnd < n - 1; secondEnd++) {
      if (num[secondStart] === '0' && secondEnd !== secondStart) break;
      if (isValid(secondStart, secondEnd, num)) return true;
    }
  }

  return false;
}
// @lc code=end
